typedef unsigned long long UINT64;
typedef unsigned int UINT32;

/* initial permutation:
   58 50 42 34 26 18 10 2
   60 52 44 36 28 20 12 4
   62 54 46 38 30 22 14 6
   64 56 48 40 32 24 16 8
   57 49 41 33 25 17 9 1
   59 51 43 35 27 19 11 3
   61 53 45 37 29 21 13 5
   63 55 47 39 31 23 15 7
*/
UINT64 init_permutation(UINT64 x)
{
  UINT64 mask0 = 0x0101010101010101;
  UINT64 sx[8];
  for (int i=0; i<8; i++) {
    UINT64 t = x & (mask0<<i);
    t <<= (7-i); // move the lowest bit to the 8th bit
    sx[i] = 0;
    sx[i] |= t;
    sx[i] |= t>>9;
    sx[i] |= t>>18;
    sx[i] |= t>>27;
    sx[i] |= t>>36;
    sx[i] |= t>>45;
    sx[i] |= t>>54;
    sx[i] |= t>>63;
    sx[i] &= 0xff;
  }
  return (sx[1])|(sx[3]<<8)|(sx[5]<<16)|(sx[7]<<24)
    |(sx[0]<<32)|(sx[2]<<40)|(sx[4]<<48)|(sx[6]<<56);
}

/* final permutation (invIP):
   40 8 48 16 56 24 64 32
   39 7 47 15 55 23 63 31
   38 6 46 14 54 22 62 30
   37 5 45 13 53 21 61 29
   36 4 44 12 52 20 60 28
   35 3 43 11 51 19 59 27
   34 2 42 10 50 18 58 26
   33 1 41 9 49 17 57 25
*/
UINT64 final_permutation(UINT64 x)
{
  UINT64 mask0 = 0x0101010101010101;
  UINT64 sx[8];
  for (int i=0; i<8; i++) {
    UINT64 t = x & (mask0<<i);
    t <<= (7-i);
    sx[i] = 0;
    sx[i] |= t>>6;
    sx[i] |= t>>12;
    sx[i] |= t>>18;
    sx[i] |= t>>24;
    sx[i] |= t>>39;
    sx[i] |= t>>45;
    sx[i] |= t>>51;
    sx[i] |= t>>57;
    sx[i] &= 0xff;
  }
  return (sx[7])|(sx[6]<<8)|(sx[5]<<16)|(sx[4]<<24)
    |(sx[3]<<32)|(sx[2]<<40)|(sx[1]<<48)|(sx[0]<<56);
}

/* expansion:
   32 1 2 3 4 5
   4 5 6 7 8 9
   8 9 10 11 12 13
   12 13 14 15 16 17
   16 17 18 19 20 21
   20 21 22 23 24 25
   24 25 26 27 28 29
   28 29 30 31 32 1

   @input: 32bit data
   @output: expanded 48bit data, stored in UINT64[0:47]
*/

UINT64 expansion(UINT32 k)
{
  // k[32,1:5]
  UINT64 r = (k>>31)|((k&0x1f)<<1);
  // k[4:9]
  r |= (k&0x1f8)<<3;
  // k[8:13]
  r |= (k&0x1f80)<<5;
  // k[12:17]
  r |= (k&0x1f800)<<7;
  // k[16:21]
  r |= (k&0x1f8000)<<9;
  // k[20:25]
  r |= (k&0x1f80000)<<11;
  // k[24:29]
  r |= (k&0x1f800000)<<13;
  // k[28:32,1]
  r |= ((k&0xf8000000)<<15)|(((UINT64)k&1)<<47);
  return r;
}

/* permutation: half block shuffle
   16 7 20 21 29 12 28 17
   1 15 23 26 5 18 31 10
   2 8 24 14 32 27 3 9
   19 13 30 6 22 11 4 25
*/

/*
static inline
UINT32
setbit32(UINT32 x, int b, int v)
{
  return x | (v<<b);
}
*/

#define setbit(x,b,v) ((x)|((v)<<(b)))

UINT32 permutation32(UINT32 x)
{
  static int P32[32] = {
    16, 7, 20, 21, 29, 12, 28, 17,
    1, 15, 23, 26, 5, 18, 31, 10,
    2, 8, 24, 14, 32, 27, 3, 9,
    19, 13, 30, 6, 22, 11, 4, 25
  };
  UINT32 r = 0;
  for (int i=0; i<32; i++) {
    r = setbit(r, i, (x>>(P32[i]-1))&1);
  }
  return r;
}

/* permuted choice:
   left:
   57 49 41 33 25 17 9
   1 58 50 42 34 26 18
   10 2 59 51 43 35 27
   19 11 3 60 52 44 36
   right:
   63 55 47 39 31 23 15
   7 62 54 46 38 30 22
   14 6 61 53 45 37 29
   21 13 5 28 20 12 4

   @input: 64-bit input key
   @output: 56-bit round key
*/

UINT64 PC1(UINT64 k)
{
  UINT64 r = 0;
  UINT64 s[7];
  for (int i=0; i<7; i++) {
    UINT64 t = (k>>i)&0x0101010101010101;
    s[i] = t>>56;
    s[i] |= t>>47;
    s[i] |= t>>38;
    s[i] |= t>>29;
    s[i] |= t>>20;
    s[i] |= t>>11;
    s[i] |= t>> 2;
    s[i] |= t<< 7;
    s[i] &= 0xff;
  }
  r |= s[0] | (s[1]<<8) | (s[2]<<16) | ((s[3]<<24)&&0xf);
  r |= (s[6]<<28) | (s[5]<<36) | (s[4]<<44) | ((s[3]>>4)<<52);
  return r;
}

/* permuted choice 2:
   14 17 11 24 1 5 3 28
   15 6 21 10 23 19 12 4
   26 8 16 7 27 20 13 2
   41 52 31 37 47 55 30 40
   51 45 33 48 44 49 39 56
   34 53 46 42 50 36 29 32

   @input: 56-bit round key
   @output: 48-bit sub key
*/

UINT64 PC2(UINT64 k)
{
  static int PCV[56] = {
    14, 17, 11, 24, 1, 5, 3, 28,
    15, 6, 21, 10, 23, 19, 12, 4,
    26, 8, 16, 7, 27, 20, 13, 2,
    41, 52, 31, 37, 47, 55, 30, 40,
    51, 45, 33, 48, 44, 49, 39, 56,
    34, 53, 46, 42, 50, 36, 29, 32
  };
  UINT64 r = 0;
  for (int i=0; i<48; i++) {
    r = setbit(r, i, (k>>(PCV[i]-1))&1);
  }
  return r;
}

static UINT32 S0[64] = {
  14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
  0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
  4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
  15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13
};

static UINT32 S1[64] = {
  15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
  3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
  0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
  13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9
};

static UINT32 S2[64] = {
  10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
  13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
  13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
  1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12
};

static UINT32 S3[64] = {
  7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
  13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
  10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
  3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14
};

static UINT32 S4[64] = {
  2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
  14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
  4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
  11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3
};

static UINT32 S5[64] = {
  12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
  10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
  9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
  4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13
};

static UINT32 S6[64] = {
  4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
  13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
  1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
  6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12
};

static UINT32 S7[64] = {
  13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
  1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
  7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
  2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11
};

static UINT32 *DES_sbox[8] = {
  S0, S1, S2, S3, S4, S5, S6, S7
};

UINT32
substitute(int id, UINT32 input)
{
  int row = ((input&0x20)>>4)|(input&1);
  int column = (input>>1)&0xf;
  return DES_sbox[id][row*16+column];
}
